week9 HW 戴偉璿
1.
(a)
P→Q=P→f1(n)→f2(f1(n))→f3(f2(f1(n)))
複雜度為O(f1(n),f2(n),f3(n))=O(max(f1(n),f2(n),f3(n)))
(b)
3.
將輸入的n個數值進行編號並使其由小到大排列,以1,4,2,8,5,7為例,可以編號為(0,1),(1,4),(2,2),(3,8),(4,5),(5,7)四點,將其轉換成二維點後,尋找最近點對之距離,如果是等於1的話便表示有數字重複,反之則否。
4.
開另一個陣列b[],將其中的數值皆設為零。然後歷遍原輸入陣列a[],對於第i項,將bai設為1代表該數字已經被用過了。如此,若遇到一個數字ak,其數值在b[]對應到的bak不為零時,可以確定該數字重複。
本作法時間複雜度為O(n),額外空間需求O(n),並且不會更改到原輸入陣列。